home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 3186 < prev    next >
Encoding:
Text File  |  1996-08-06  |  5.4 KB  |  131 lines

  1. Newsgroups: comp.lang.java,comp.lang.c,comp.lang.c++
  2. Path: netcom.com!NewsWatcher!user
  3. From: hbaker@netcom.com (Henry Baker)
  4. Subject: Correct mod/rem (was: Problem with % (remainder) operator
  5. Message-ID: <hbaker-2201961022380001@10.0.2.15>
  6. Sender: hbaker@netcom12.netcom.com
  7. Organization: nil organization
  8. References: <4dc86s$gha@news.xs4all.nl> <4d8hnd$74h@news.xs4all.nl> <443322587wnr@almide.demon.co.uk> <142091149wnr@almide.demon.co.uk> <4dguci$le3@news.ox.ac.uk>
  9. Date: Mon, 22 Jan 1996 18:22:38 GMT
  10.  
  11. This problem has been discussed ad nauseum in every single comp.lang
  12. newsgroup, and it seems to be that every language gets it wrong in the
  13. first n iterations, so that the implementers of the new languages keep
  14. copying the wrong code from their previous language.
  15.  
  16. The usual justification for getting it wrong is that 'that's what the
  17. hardware does, and we want fast code'.  Of course, once the language gets
  18. established and _portability_ to a wide variety of machines becomes important,
  19. it becomes necessary to try to retrofit a fully specified function, thus
  20. breaking many existing programs.
  21.  
  22. So far as I know, only APL and Common Lisp have attempted to get 'mod' right.
  23.  
  24. 'Everybody' thinks they know how division works, because they all learned it
  25. in graded school.
  26.  
  27. OK, so what did you learn?  Given a 'dividend' N and a 'divisor' D, we need
  28. to compute a 'quotient' Q, and a 'remainder' R.  What properties do we want
  29. from this quotient Q and this remainder R?
  30.  
  31. The first property is that N = Q*D + R.  Otherwise, the whole meaning of
  32. 'remainder' is lost -- i.e., that part that 'remains' after taking out Q
  33. copies of D from N.
  34.  
  35. Fine, so we simply set Q=0, R=N.  'You can't do that," you say.  Why?  Because
  36. then division didn't _do_ anything, it didn't make R 'small'.
  37.  
  38. Why do we need R 'small'?  Well, if we're converting binary to decimal, and
  39. we divide our binary number by 10 and get as a remainder our original binary
  40. number, we will need an awful lot of decimal 'digits' :-).  So, using base
  41. conversion as a _criterion_, we add the additional constraint that
  42.  
  43. 0 <= |R| < |D|.
  44.  
  45. In other words, we want the absolute value of the 'remainder' to be smaller
  46. than the absolute value of the divisor.
  47.  
  48. However, this still doesn't pin down the answer.  For example, if we divide
  49. 27 by 10, we can get two different quotients and remainders:
  50.  
  51. (I)     27 = 2*10 + 7         i.e., Q=2, R=7
  52.  
  53. (II)    27 = 3*10 + (-3)      i.e., Q=3, R=-3
  54.  
  55. Going back to our decimal conversion problem again, we decide that the
  56. most appropriate choice is the first, not the second, since we want base
  57. conversion to 'work' correctly.
  58.  
  59. We therefore refine our constraints, but find that we still have two choices
  60. when the divisor is _negative_.
  61.  
  62. (I)     0 <= R < |D|
  63.  
  64. (II)    0 <= R*D < D^2
  65.  
  66. For example, if we divide 27 by -10, we can still get two different quotients
  67. and remainders:
  68.  
  69. (I)     27 = (-2)*(-10) + 7     i.e., Q=-2, R=7
  70.  
  71. (II)    27 = (-3)*(-10) + (-3)  i.e., Q=-3, R=-3
  72.  
  73. Once again, we appeal to the base conversion algorithm for our answer.  In
  74. the case of a negative divisor, we _expect_ negative digits -- indeed, we
  75. _demand_ them, so that the correct choice is (II), which can be expressed
  76. by the rule "sign of remainder follows sign of the divisor" (NOT, sign of
  77. the dividend, like lots of brain-damaged computer hardware).
  78.  
  79. The nice thing about the "sign of the divisor" choice is that the quotient
  80. is easily expressed as the 'floor' function:  Q = floor[N/D].
  81.  
  82. ----
  83.  
  84. There is another division function called 'round' which tries to find the
  85. 'closest' integer to the rational quotient.  As might be expected, the
  86. remainders produced by 'round' are smaller than those produced by 'floor',
  87. and are both positive and negative:
  88.  
  89. 0 <= |R| <= |D|/2
  90.  
  91. This is well-defined if D is an odd integer, but is ambiguous if D is even.
  92. There are several competing definitions for what to do if D is even: one of
  93. them is 'if N/D falls half way between two integers, choose the even one
  94. as the quotient'.  This rule is similar to one that is used by numerical
  95. analysts as an 'unbiased' rounding rule, and is used by some IEEE float
  96. implementations.
  97.  
  98. Base conversion sometimes uses remainders produced by 'round' instead of
  99. 'floor'.  For example, hardware multipliers often convert to a 'balanced'
  100. notation.  If we were doing decimal, then we would use the 'digits'
  101. -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, instead of 5, 6, 7, 8, 9, 0, 1, 2, 3, 4,
  102. respectively, because it reduces the number of carries that have to propagate.
  103.  
  104. (Those who know about implementations of GCD, also know that 'round' produces
  105. the GCD in the least number of iterations.)
  106.  
  107. -----
  108.  
  109. To summarize, the 'correct' mod is one that produces remainders that follow
  110. the _divisor_, and therefore the 'correct' quotient is the _floor_ function.
  111. If your language allows more than one, then the next one should be the
  112. 'round' function (& least absolute remainders).
  113.  
  114. Unless you plan for your language to run on only one machine, make the
  115. quotient and mod functions _well-defined_, so that portability is ensured.
  116.  
  117. ----
  118.  
  119. You might find additional insight in the paper
  120.  
  121. ftp://ftp.netcom.com/pub/hb/hbaker/Gaussian.html  (also .ps.Z)
  122.  
  123. -- 
  124. www/ftp directory:
  125. ftp://ftp.netcom.com/pub/hb/hbaker/home.html
  126.  
  127. Copyright (c) 1996 by Henry G. Baker.  All rights reserved.
  128. ** Warning: Due to its censorship, CompuServe and its subscribers **
  129. ** are expressly prohibited from storing or copying this document **
  130. ** in any form.                                                   **
  131.